googologywikiaorg-20200223-history
User blog:P進大好きbot/Elementary Large Number beyond ψ 0(Ω ω)
I define an elementary large function \(f(x)\) beyond \(\psi_0(\Omega_{\omega}) = \textrm{PTO}(\Pi_1^1 \textrm{-CA}_0)\) in FGH, where \(\psi\) denotes Buchholz's OCF. This is an extension of the technique in my another elementary large function \(\textrm{AC}_1\) beyond \(\varepsilon_0\) in FGH. Although it is quite easy to extend it to a function beyond \(\textrm{PTO}(\Pi_1^1 \textrm{-TR}_0) = \psi_{\Omega}(\psi_I(0))\), where \(\psi\) and \(I\) denote Rathjen's OCF with weakly inaccessible and the least weakly inaccessible cardinal respectively, it makes the definition hard to read. Therefore I stop extending the same technique. I note that in the definition of \(f\), I only use elementary operators (the addition \(x + y\), the subtraction \(x - y\), the multipliciation \(x \times y\), the division \(\frac{x}{y}\), and the power \(x^y\)) and four other single variable functions (\(v(x)\), \(\triangleleft(x)\), \(\downarrow(x)\), and \(\Delta(x)\)) which I will explicitly define by only using those operators. That is why I say that \(f\) is elementary. Yeah, I know that it looks a bit saladified anyway. Creating a large function beyond such an OCF-level ordinal without using multivariable recursions often causes such saladability. At least, it is well-defined if there is no mistake. Definition Let \(\mathbb{N}\) denote the set of natural numbers, and \(\mathbb{N}_{+} \subset \mathbb{N}\) the subset of positive integers. I define a computable function \begin{eqnarray*} v(x) \colon \mathbb{N}_{+} & \to & \mathbb{N} \\ x & \mapsto & v(x) \end{eqnarray*} as the maximum of an \(i \in \mathbb{N}\) satisfying \(\frac{x}{2^i} \in \mathbb{N}_{+}\). I define computable functions \begin{eqnarray*} \triangleleft \colon \mathbb{N}_{+} & \to & \mathbb{N}_{+} \\ x & \mapsto & \triangleleft(x) \\ \downarrow \colon \mathbb{N}_{+} & \to & \mathbb{N}_{+} \\ x & \mapsto & \downarrow(x) \end{eqnarray*} simultaneously in the following recursive way: # Put \(n := v(x)\). # Put \(a := \frac{x}{2^n}\). # Denote by \(y\) the maximum of an \(i \in \mathbb{N}\) satisfying \(2^i \leq a\). # Suppose \(y \leq 1\). ## Put \(\triangleleft(x) := a\). ## Put \(\downarrow(x) := 1\). # Suppose \(y > 1\) and \(a = 2^y + 1\). ## Put \(m := v(y)\). ## Put \(b := \frac{y}{2^m}\). ## Suppose \(\triangleleft(b) = 1\). ### Put \(\triangleleft(x) := a\). ### Put \(\downarrow(x) := 2^n + 1\). ## Suppose \(\triangleleft(b) = 3\). ### Put \(\triangleleft(x) := 9\). ### Put \(z := 2^m \downarrow(b)\). ### Put \(\downarrow(x) := \frac{2^{xz} - 1}{2^z - 1}\). ## Suppose \(\triangleleft(b) = 9\). ### Put \(\triangleleft(x) := 9\). ### Put \(\downarrow(x) := 2^{2^m \downarrow(2^x b)} + 1\). ## Suppose \(\triangleleft(b) \neq 1,3,9\) and \(2^{2^m} + 1 < \triangleleft(b)\). ### Put \(\triangleleft(x) := 9\). ### Suppose \(n = 0\). #### Put \(z := 2^m \downarrow(2^{2^{v^2(\triangleleft(b) - 1) - 1}} b)\). #### Put \(\downarrow(x) := 2^z + 1\). ### Suppose \(n > 0\). #### Put \(z := 2^m \downarrow((\downarrow(\frac{x}{2}) - 1)b)\). #### Put \(\downarrow(x) := 2^z + 1\). ## Suppose \(\triangleleft(b) \neq 1,3,9\) and \(2^{2^m} + 1 \geq \triangleleft(b)\). ### Put \(\triangleleft(x) := \triangleleft(b)\). ### Put \(\downarrow(x) := 2^{2^m \downarrow(2^n b)} + 1\). # Suppose \(y > 1\) and \(a \neq 2^y + 1\). ## Denote by \(w\) the minimum of an \(i \in \mathbb{N}_{+}\) satisfying \(2^{y-i} + 2^y \leq a\). ## Put \(\triangleleft(x) := \triangleleft(2^w + 1)\). ## Put \(\downarrow(x) := 2^z(a - 2^y + 2^{y-w}(\downarrow(2^n(2^w + 1)) - 1))\). I define a computable function \begin{eqnarray*} \Delta \colon \mathbb{N} & \to & \mathbb{N} \\ x & \mapsto & \Delta(x) \end{eqnarray*} in the following recursive way: # Put \(n := v(x)\). # Put \(a := \frac{x}{2^n}\). # If \(a = 1\), then put \(\Delta(x) := 2^x\). # If \(a \neq 1\), then put \(\Delta(x) := 2^{\Delta^x(2^x \downarrow(x))} x\). I define a computable function \begin{eqnarray*} f \colon \mathbb{N} & \to & \mathbb{N} \\ x & \mapsto & f(x) \end{eqnarray*} by putting \(f(x) := \Delta(2^{2^x} + 1)\). Then \(f(10^{100})\) is an elementary large number. Analysis As I wrote in the beginning, the growth rate of \(f\) is greater than that of \(f_{\psi_0(\Omega_{\omega})}\) with respect to FGH and Buchholz's OCF. Further, I guess that it is bounded by that of \(f_{\psi_0(\Omega_{\omega}) + 1}\) with respect to FGH. In order to verify this upperbound, I need to estimate the behaviour of the lengths of ordinal terms in Buchholz's ordinal notation system. It seems not to be so difficult, but to be tiresome. I appreciate anyone's precise estimation. Category:Blog posts